package test.n00400;


import static utils.Tools.listOf;

public class Problem00450 {
    public static void main(String[] args) {
        println(new int[]{2, 3, 1, 1, 4});
    }

    public static void println(int[] nums) {
        Solution ss = new Solution();
        System.out.println(listOf(nums) + "," + listOf(ss.jump(nums)));
    }

    public static class Solution {

        /**
         * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
         * <p>
         * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
         * <p>
         * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
         * <p>
         * 假设你总是可以到达数组的最后一个位置。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/jump-game-ii
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         * <p>
         * 解题思路:
         * 反向查找+贪心算法
         *
         * @param nums
         * @return
         */
        public int jump(int[] nums) {
            int position = nums.length - 1;
            int steps = 0;
            // 先找到最后一挑的位置
            // 再再到倒数第二的位置，直到第0个位置
            while (position > 0) {

                for (int i = 0; i < position; i++) {
                    if (i + nums[i] >= position) {
                        position = i;
                        steps++;
                        break;
                    }
                }
            }
            return steps;
        }
    }
}
